#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "stack.h"

int InitStack(SqStack *s)
{
	s->base = (SELemType*)malloc(STACK_INIT_SIZE * sizeof(SELemType));
	if (!s->base)
		return -1;
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
	return 0;
}

int DestroyStack(SqStack *s)
{
	if(s->base)
		free(s->base);
	return 0;
}

int InitStackAry(SqStack *s, SELemType* ary)
{
	s->base = ary;
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
	return 0;
}

int DestroyStackAry(SqStack *s)
{
	return 0;
}

//set s to NULL stack
int ClearStack(SqStack *s)
{
	s->top = s->base;
	return 0;
}

//if stack is NULL,
//return 1 if NULL; else return 0
int StackEmpty(SqStack *s)
{
	if (s->top == s->base)
		return 1;
	return 0;
}

//return item number
int StackLength(SqStack *s)
{
	return s->stacksize;
}

int Push(SqStack *s, SELemType e)
{
	if(s->top - s->base >= s->stacksize) {
		printf("stack overflow \n");
		return -1;
	}
	*s->top = e;
	s->top++;
	return 0;
}

int GetTop(SqStack *s, SELemType* e)
{
	if(StackEmpty(s))
		return -1;
	*e = *(s->top - 1);
	return 0;
}

SELemType GetTopVal(SqStack *s)
{
	SELemType val;
	GetTop(s, &val);
	return val;
}


int Pop(SqStack *s, SELemType *e)
{
	if(StackEmpty(s))
		return -1;
	s->top--;
	*e = *(s->top);
	return 0;
}

void test_stack(void)
{
	SqStack s;
	SELemType i, val;
	SELemType n = 20;

	InitStack(&s);

	printf("start push\n");
	for(i = 0; i < n; i++) {
		printf("%d ", i + 1);
		Push(&s, i + 1);
	}
	printf("\n");

	printf("start pop\n");
	for(i = 0; i < n; i++) {
		Pop(&s, &val);
		printf("%d ", val);
	}
	printf("\n\n");

	DestroyStack(&s);
}

/*
 * https://blog.csdn.net/liangxingda/article/details/52806173?spm=1001.2014.3001.5501
 * 所谓的逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。（摘自维基）

　　数学表达式a+b，就是一种中缀表达式，写成后缀表达式就是ab+   
	中缀表达式(a+b)*c-(a+b)/e的逆波兰式是ab+c*ab+e/-

(1)首先，需要分配2个栈，栈s1用于临时存储运算符（含一个结束符号），此运算符在栈内遵循越往栈顶优先级越高的原则；栈s2用于输入逆波兰式，为方便起见，栈s1需先放入一个优先级最低的运算符，在这里假定为'#'；

(2)从中缀式的左端开始逐个读取字符x，逐序进行如下步骤：

　1.若x是操作数，则分析出完整的运算数（在这里为方便，用字母代替数字），将x直接压入栈s2；

　2.若x是运算符，则分情况讨论：

　　　　若x是'('，则直接压入栈s1；

　　　　若x是')'，则将距离栈s1栈顶的最近的'('之间的运算符，
		逐个出栈，依次压入栈s2，此时抛弃'('；

　　　　若x是除'('和')'外的运算符，则再分如下情况讨论：

　　　　　　若当前栈s1的栈顶元素为'('，则将x直接压入栈s1；

　　　　　　若当前栈s1的栈顶元素不为'('，则将x与栈s1的栈顶元素比较，若x的优先级大于栈s1栈顶运算符优先级，则将x直接压入栈s1。否者，将栈s1的栈顶运算符弹出，压入栈s2中，直到栈s1的栈顶运算符优先级别低于（不包括等于）x的优先级，或栈s2的栈顶运算符为'('，此时再则将x压入栈s1;

(3)在进行完(2)后，检查栈s1是否为空，若不为空，则将栈中元素依次弹出并压入栈s2中（不包括'#'）；　　　　　　


(4)完成上述步骤后，栈s2便为逆波兰式输出结果。
但是栈s2应做一下逆序处理，因为此时表达式的首字符位于栈底；
 * */

/*
 * 一般的表达式：中缀表达式，中序遍历
 * 波兰表达式：前缀表达式，用树存储，用于编译C语言等，前序遍历
 * 逆波兰表达式：栈存贮，编译，后序遍历
 * */
char ary1[STACK_INIT_SIZE];
char ary2[STACK_INIT_SIZE];

void polanshi(char* e)
{
	SqStack s1, s2;
	char* p = e, ch;
	int length = 0;
	char result[STACK_INIT_SIZE];

	InitStackAry(&s1, ary1);
	InitStackAry(&s2, ary2);
	Push(&s1, '#');

	for (; *p; p++) {
		switch (*p) {
			case '(':
				Push(&s1, *p);
				break;
			case')':
				while (GetTopVal(&s1) != '(') {
					Pop(&s1, &ch);
					Push(&s2, ch);
				}
				Pop(&s1, &ch);
				break;
			case'+':
			case'-':
				for (ch = GetTopVal(&s1); ch != '#'; ch = GetTopVal(&s1)) {
					if (ch == '(')
						break;
					else { 
						Pop(&s1, &ch);
						Push(&s2, ch);
					}
				}
				Push(&s1, *p);
				length++;
				break;
			case'*':
			case'/':
				for (ch = GetTopVal(&s1); ch != '#' && ch != '+' && ch != '-';
						ch = GetTopVal(&s1)) {
					if (ch == '(')
						break;
					else { 
						Pop(&s1, &ch);
						Push(&s2, ch);
					}
				}
				Push(&s1, *p);
				length++;
				break;
			default:
				Push(&s2, *p);
				length++;
		}//end switch
	}//end for

	while (!StackEmpty(&s1) && GetTopVal(&s1) != '#') { 
		Pop(&s1, &ch); 
		Push(&s2, ch); 
	}

	result[length] = 0;
	p = result + length - 1;
	for (int i = 0; !StackEmpty(&s2); i++, p--) { 
		Pop(&s2, &ch); 
		*p = ch; 
	}

	DestroyStackAry(&s1);
	DestroyStackAry(&s2);
	printf("Reverse Polish: %s\n", result);
}

void  test_polan(void)
{
	char e[100];
	//scanf("%s", e);
	//strcpy(e, "a+b");
	strcpy(e, "(a+b)*c-(a+b)/e");
	printf("ori expression: %s\n", e);
	polanshi(e);
	printf("\n");
}

int main(int argc, char** argv)
{
	test_stack();
	test_polan();
	return 0;
}


